If you are doing breadth first search and are finding the shortest path to the state you know how to represent it and that there is only one such state, then two-way BFS could be applied.
It searches the graph from start state and end state and if the frontier of the searched cross, you can track the shortest path.
One example you can apply it is solving two-way rubik's cube.
This is actually an assignment to https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-fall-2011/.
So for the rubik library in the below code, you can find it from the link.
Note that when there is no solution, that is, when end state is unreachable from the start state, two-way BFS gives no speedup. On the contrary, it searches the whole graph twice.
import Queue
import rubik
def track_moves(parent_primary, parent_secondary, last_position, start):
if start:
parent_from_start = parent_primary
parent_from_end = parent_secondary
else:
parent_from_start = parent_secondary
parent_from_end = parent_primary
position = last_position
moves = []
while parent_from_start[position]:
position, twist = parent_from_start[position]
moves.append(twist)
# reverse list
moves.reverse()
position = last_position
while parent_from_end[position]:
position, twist = parent_from_end[position]
moves.append(twist)
return moves
def bfs_routine(parent_primary, parent_secondary, queue, start):
position = queue.get()
next_positions = [(rubik.perm_apply(twist, position), twist) for twist in
rubik.quarter_twists] if start else \
[(rubik.perm_apply(rubik.perm_inverse(twist), position), twist) for twist in
rubik.quarter_twists]
for next_position, twist in next_positions:
if next_position not in parent_primary:
parent_primary[next_position] = (position, twist)
queue.put(next_position)
if next_position in parent_secondary:
print next_position
return track_moves(parent_primary, parent_secondary,
next_position, start)
return None
def shortest_path(start, end):
"""
Using 2-way BFS, finds the shortest path from start_position to
end_position. Returns a list of moves.
You can use the rubik.quarter_twists move set.
Each move can be applied using rubik.perm_apply
"""
# answer is a list of rubik.quarter_twists moves
# each of which is a permutation corresponding to a move on a pocket cube
# next states from one is generated by perm_apply(t, position)
# where t is an element of rubik.quarter_twists and current position
# that is a permutaitonf a tuple of length 24 whose element is 0..23
if start == end:
return []
parent_from_start = {}
parent_from_end = {}
queue_start = Queue.Queue()
queue_end = Queue.Queue()
queue_start.put(start)
queue_end.put(end)
parent_from_start[start] = None
parent_from_end[end] = None
while not queue_start.empty() or not queue_end.empty():
start_result = bfs_routine(parent_from_start, parent_from_end,
queue_start, start=True)
if start_result is not None:
return start_result
end_result = bfs_routine(parent_from_end, parent_from_start,
queue_end, start=False)
if end_result is not None:
return end_result
return None